package challenge._2021;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 说明
 * 准备参加计算机能力挑战赛的小邹最近在努力刷题，他迷上了回文数并且久久写不出这题的答案，你能帮帮他吗？
 * 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
 *
 * 例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。
 * 又如：对于10进制数87：
 * STEP1：87+78 = 165 STEP2：165+561 = 726
 * STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
 * 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
 *
 * 写一个程序，给定一个N（2<=N<=10或N=16）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
 *
 * 如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
 *
 * 输入格式
 * 输入描述:
 * 两行，N与M
 *
 * 输入样例:
 * 9
 * 87
 *
 * 输出格式
 * 输出描述:
 * 如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）
 * 输出样例:
 * STEP=6
 * @since 2022 - 11 - 17 - 16:49
 */
public class _07力战趣味回文数 {
}
class Main7{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String num = sc.next();
        int cnt = 0;
        while(cnt++ <= 30){
            num = add(num, get(num), n);
            if(check(num)){
                System.out.println("STEP=" + cnt);
                return;
            }
        }
        System.out.println("Impossible!");
    }
    //检查是否回文
    static boolean check(String s){
        int left = 0, right = s.length() - 1;
        while(left < right){
            if(s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    //得到逆向串
    static String get(String num){
        StringBuilder builder = new StringBuilder();
        for(int i = num.length() - 1; i >= 0; i--)
            builder.append(num.charAt(i));
        return builder.toString();
    }
    //n进制加法
    static String add(String n1, String n2, int n){
        int carry = 0;
        StringBuilder builder = new StringBuilder();
        int num1, num2;
        char bit;
        int b;
        for(int i = n1.length() - 1; i >= 0; i--){
            num1 = n1.charAt(i) >= 'A' ? n1.charAt(i) - 'A' + 10 : n1.charAt(i) - '0';
            num2 = n2.charAt(i) >= 'A' ? n2.charAt(i) - 'A' + 10 : n2.charAt(i) - '0';
            b = (num1 + num2 + carry) % n;
            bit = (b > 9) ? (char)(b - 10 + 'A') : (char)(b + '0');
            builder.append(bit);
            carry = num1 + num2 + carry >= n ? 1 : 0;
        }
        if(carry > 0){
            builder.append('1');
        }
        return builder.reverse().toString();
    }
}